#include <iostream>
#include <cmath>
#include <cstdlib>
#include <memory>
#include <vector>

using namespace std;

struct node
{
	int n;
	int degree;
	weak_ptr<node> parent;
	shared_ptr<node> child;
	shared_ptr<node> left;
	shared_ptr<node> right;
	char mark;
	char C;
};

class FibonacciHeap
{
private:
	int nH;
	shared_ptr<node> H;
public:
	shared_ptr<node> MakeHeap();  
	shared_ptr<node> insert(int);
	shared_ptr<node> union(shared_ptr<node>, shared_ptr<node>);
	shared_ptr<node> extractMin(shared_ptr<node>);
    shared_ptr<node> Find(shared_ptr<node>, int);
	int decreaseKey(shared_ptr<node>, int, int);
	int deleteKey(shared_ptr<node>, int);
private:
	int Fibonnaci_link(shared_ptr<node>, shared_ptr<node>, shared_ptr<node>);
	shared_ptr<node> create_node(int);
	int Consolidate(shared_ptr<node>);
	int Cut(shared_ptr<node>, shared_ptr<node>, shared_ptr<node>);
	int Cascase_cut(shared_ptr<node>, shared_ptr<node>);

public:
	FibonacciHeap()
	{
		H = MakeHeap();
	}
};

shared_ptr<node> FibonacciHeap::MakeHeap()
{
	shared_ptr<node> np;
	np = NULL;
	return np;
}

shared_ptr<node> FibonacciHeap::create_node(int value)
{
	shared_ptr<node> x;
	x->n = value;
	return x;
}

shared_ptr<node> FibonacciHeap::insert(int k)
{
	shared_ptr<node> x = create_node(k);
	x->degree = 0;
	x->parent.lock = NULL;
	x->child = NULL;
	x->left = x;
	x->right = x;
	x->mark = 'F';
	x->C = 'N';
	if (H != NULL)
	{
		(H->left)->right = x;
		x->right = H;
		x->left = H->left;
		H->left = x;
		if (x->n < H->n)
			H = x;
	}
	else
	{
		H = x;
	}
	nH = nH + 1;
	return H;
}

int FibonacciHeap::Fibonnaci_link(shared_ptr<node> H1, shared_ptr<node> y, shared_ptr<node> z)
{
	(y->left)->right = y->right;
	(y->right)->left = y->left;
	if (z->right == z)
		H1 = z;
	y->left = y;
	y->right = y;
	y->parent = z;
	if (z->child == NULL)
		z->child = y;
	y->right = z->child;
	y->left = (z->child)->left;
	((z->child)->left)->right = y;
	(z->child)->left = y;
	if (y->n < (z->child)->n)
		z->child = y;
	z->degree++;
}

shared_ptr<node> FibonacciHeap::union(shared_ptr<node> H1, shared_ptr<node> H2)
{
	shared_ptr<node> np;
	shared_ptr<node> H = MakeHeap();
	H = H1;
	(H->left)->right = H2;
	(H2->left)->right = H;
	np = H->left;
	H->left = H2->left;
	H2->left = np;
	return H;
}

shared_ptr<node> FibonacciHeap::extractMin(shared_ptr<node> H1)
{
	shared_ptr<node> p;
	shared_ptr<node> ptr;
	shared_ptr<node> z = H1;
	p = z;
	ptr = z;
	if (z == NULL)
		return z;
	shared_ptr<node> x;
	shared_ptr<node> np;
	x = NULL;
	if (z->child != NULL)
		x = z->child;
	if (x != NULL)
	{
		ptr = x;
		do
		{
			np = x->right;
			(H1->left)->right = x;
			x->right = H1;
			x->left = H1->left;
			H1->left = x;
			if (x->n < H1->n)
				H1 = x;
			x->parent.lock = NULL;
			x = np;
		} while (np != ptr);
	}
	(z->left)->right = z->right;
	(z->right)->left = z->left;
	H1 = z->right;
	if (z == z->right && z->child == NULL)
		H = NULL;
	else
	{
		H1 = z->right;
		Consolidate(H1);
	}
	nH = nH - 1;
	return p;
}

int FibonacciHeap::Consolidate(shared_ptr<node> H1)
{
	int d, i;
	float f = (log(nH)) / (log(2));
	int D = f;
	vector< shared_ptr<node> > A;
	A.resize[d];
	for (i = 0; i <= D; i++)
		A[i] = NULL;
	shared_ptr<node> x = H1;
	shared_ptr<node> y;
	shared_ptr<node> np;
	shared_ptr<node> pt = x;
	do
	{
		pt = pt->right;
		d = x->degree;
		while (A[d] != NULL)
		{
			y = A[d];
			if (x->n > y->n)
			{
				np = x;
				x = y;
				y = np;
			}
			if (y == H1)
				H1 = x;
			Fibonnaci_link(H1, y, x);
			if (x->right == x)
				H1 = x;
			A[d] = NULL;
			d = d + 1;
		}
		A[d] = x;
		x = x->right;
	} while (x != H1);
	H = NULL;
	for (int j = 0; j <= D; j++)
	{
		if (A[j] != NULL)
		{
			A[j]->left = A[j];
			A[j]->right = A[j];
			if (H != NULL)
			{
				(H->left)->right = A[j];
				A[j]->right = H;
				A[j]->left = H->left;
				H->left = A[j];
				if (A[j]->n < H->n)
					H = A[j];
			}
			else
			{
				H = A[j];
			}
			if (H == NULL)
				H = A[j];
			else if (A[j]->n < H->n)
				H = A[j];
		}
	}
}

int FibonacciHeap::decreaseKey(shared_ptr<node>H1, int x, int k)
{
	shared_ptr<node> y;
	if (H1 == NULL)
	{
		cout << "The Heap is Empty" << endl;
		return 0;
	}
	shared_ptr<node> ptr = Find(H1, x);
	if (ptr == NULL)
	{
		cout << "node not found in the Heap" << endl;
		return 1;
	}
	if (ptr->n < k)
	{
		cout << "Entered key greater than current key" << endl;
		return 0;
	}
	ptr->n = k;
	y = ptr->parent.lock;
	if (y != NULL && ptr->n < y->n)
	{
		Cut(H1, ptr, y);
		Cascase_cut(H1, y);
	}
	if (ptr->n < H->n)
		H = ptr;
	return 0;
}

int FibonacciHeap::Cut(shared_ptr<node> H1, shared_ptr<node> x, shared_ptr<node> y)
{
	if (x == x->right)
		y->child = NULL;
	(x->left)->right = x->right;
	(x->right)->left = x->left;
	if (x == y->child)
		y->child = x->right;
	y->degree = y->degree - 1;
	x->right = x;
	x->left = x;
	(H1->left)->right = x;
	x->right = H1;
	x->left = H1->left;
	H1->left = x;
	x->parent.lock = NULL;
	x->mark = 'F';
}

int FibonacciHeap::Cascase_cut(shared_ptr<node> H1, shared_ptr<node> y)
{
	shared_ptr<node> z = y->parent.lock;
	if (z != NULL)
	{
		if (y->mark == 'F')
		{
			y->mark = 'T';
		}
		else
		{
			Cut(H1, y, z);
			Cascase_cut(H1, z);
		}
	}
}

shared_ptr<node> FibonacciHeap::Find(shared_ptr<node> H, int k)
{
	shared_ptr<node> x = H;
	x->C = 'Y';
	shared_ptr<node> p = NULL;
	if (x->n == k)
	{
		p = x;
		x->C = 'N';
		return p;
	}
	if (p == NULL)
	{
		if (x->child != NULL)
			p = Find(x->child, k);
		if ((x->right)->C != 'Y')
			p = Find(x->right, k);
	}
	x->C = 'N';
	return p;
}

int FibonacciHeap::deleteKey(shared_ptr<node> H1, int k)
{
	shared_ptr<node> np = NULL;
	int t;
	t = decreaseKey(H1, k, -5000);
	if (!t)
		np = extractMin(H);
	return 0;
}
